package j2025.j05;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author 猫大仙
 */
public class j0512 {
    List<List<Integer>> ret;
    List<Integer> path;
    public List<List<Integer>> subsets(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        dfs(nums,0);
        return ret;
    }
    public void dfs(int[] nums,int index){
        ret.add(new ArrayList<>(path));
        for (int i = index; i < nums.length; i++) {
            path.add(nums[i]);
            dfs(nums,i+1);
            path.remove(path.size()-1);
        }
    }


    String[] phone = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    StringBuilder Path;
    List<String> Ret;

    public List<String> letterCombinations(String digits) {
        Path = new StringBuilder();
        Ret = new ArrayList<>();
        if(digits.length() == 0){
            return Ret;
        }
        DFS(digits,0);
        return Ret;
    }
    public void DFS(String digits,int index){
        if(index == digits.length()){
            Ret.add(Path.toString());
            return;
        }
        String tmp = phone[digits.charAt(index)-'0'];
        for (int i = 0; i < tmp.length(); i++) {
            Path.append(tmp.charAt(i));
            DFS(digits,index+1);
            Path.deleteCharAt(Path.length()-1);
        }
    }
}
